package algo.BackTrackSearch;
import java.util.Vector;

import java.io.*;

import java.util.*;

import algo.Common.ClassTT;
import algo.Common.Course;
import algo.Common.Data;
import algo.Common.DaySlot;
import algo.Common.Instructor;

public class BackTrackSearch {

	/**
	 * @param args
	 */
	
	VarIntTT[] var_slots;
	VarIntTT[] var_days;
	
	// store solution
	int[] sol_slots;
	int[] sol_days;
	
	int[][][] forbiden;
	int nbCourses;
	int nbClasses;
	
	Course[] courses;
	Data D;
	boolean[][] conflict;
	int nbSlots;
	int minSlot;
	int maxSlot;
	int nbDays;
	int minDay;
	int maxDay;
	boolean foundSolution = false;
	long nbSolutions = 0;
	
	BufferedWriter log = null;

	void writeLog(String msg){
		try{
			log.write(msg);
		}catch(IOException e){
			System.out.println("io exception when writing to log file");
		}
	}
	private void retrieveSolution(){
		if(foundSolution) return;
		System.out.println("found solution: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
		nbSolutions++;
		//writeLog("found solution " + nbSolutions + " !!!!!!\n");
		sol_slots = new int[var_slots.length];
		sol_days = new int[var_days.length];
		
		for(int i = 0; i < nbCourses; i++){
			sol_slots[i] = var_slots[i].getValue();
			sol_days[i] = var_days[i].getValue();
			System.out.println("Course " + i + ", " + courses[i].getName() + ": " + var_days[i].getValue() + "/" + var_slots[i].getValue());
//			try{
//				log.write("Course " + i + ", " + courses[i].getName() + ": " + var_days[i].getValue() + "/" + var_slots[i].getValue() + "\n");
//			}catch(IOException e){
//				System.out.println("io exception");
//			}
		}
		foundSolution = true;
	}
	public void TRY(int i){// try values for course i
		//System.out.println("TRY(" + i + ")");
		//System.out.print(" days = {");
		//for(int d = var_days[i].getMinValue(); d <= var_days[i].getMaxValue(); d++) if(var_days[i].isValue(d))
			//System.out.print(d + ",");
		//System.out.print("} slots = {");
		//for(int sl = var_slots[i].getMinValue(); sl <= var_slots[i].getMaxValue(); sl++) if(var_slots[i].isValue(sl))
			//System.out.print(sl + ",");
		//System.out.println("}");
		
		if(foundSolution) return;
		for(int d = var_days[i].getMinValue(); d <= var_days[i].getMaxValue(); d++) if(var_days[i].isValue(d)){
			for(int sl = var_slots[i].getMinValue(); sl <= var_slots[i].getMaxValue(); sl++) if(var_slots[i].isValue(sl)){
				if(forbiden[i][d][sl]==0 && sl + courses[i].getNbrSlots() - 1 <= nbSlots){
					var_slots[i].setValue(sl);
					var_days[i].setValue(d);
					for(int j = 0; j < i; j++) System.out.print("[" + var_days[j].getValue() + "," + var_slots[j].getValue() + "]");
					System.out.println("TRY(" + i + "), day  = " + d + " slot = " + sl);
//					try{
//						log.write("TRY(" + i + "), day  = " + d + " slot = " + sl + "\n");
//					}catch(IOException e){
//						System.out.println("IO exception");
//					}
					for(int j = i+1; j < nbCourses; j++){
						if(conflict[i][j]){
							int nbSlotj = courses[j].getNbrSlots();
							int nbSloti = courses[i].getNbrSlots();
							for(int k = 1; k <= nbSlots-nbSlotj+1; k++){
								if(!(k+nbSlotj-1 < sl || k > sl+nbSloti-1)){
									forbiden[j][d][k]++;
									//System.out.println("forbiden[" + j + "," + d + "," + k + "] = " + forbiden[j][d][k]);
									//try{
										//writeLog("TRY(" + i + ") -> mark, forbiden[" + j + "," + d + "," + k + "] = " + forbiden[j][d][k] + "\n");
									//}catch(IOException e){
										//System.out.println("io exception");
									//}
								}
							}
						}
					}
	
					if(i == nbCourses-1){
						retrieveSolution();
					}else{
						TRY(i+1);
					}					
					for(int j = i+1; j < nbCourses; j++){
						if(conflict[i][j]){
							int nbSlotj = courses[j].getNbrSlots();
							int nbSloti = courses[i].getNbrSlots();
							for(int k = 1; k <= nbSlots-nbSlotj+1; k++){
								if(!(k+nbSlotj-1 < sl || k > sl+nbSloti-1)){
									forbiden[j][d][k]--;
									//System.out.println("forbiden[" + j + "," + d + "," + k + "] = " + forbiden[j][d][k]);
									//try{
										//writeLog("TRY(" + i + ") -> recover, forbiden[" + j + "," + d + "," + k + "] = " + forbiden[j][d][k] + "\n");
									//}catch(IOException e){
										//System.out.println("io exception");
									//}
								}
							}
						}
					}
				}
			}
		}
                int iTony = 0;
	}
	
	public void search(SolutionTT sol, Data data){
		D = data;
		var_slots = sol.getSlot();
		var_days = sol.getDay();
		nbCourses = var_slots.length;
		nbDays = 5;
		minDay = D.getMinDay();
		maxDay = D.getMaxDay();
		nbSlots = 6;
		minSlot = D.getMinSlot();
		maxSlot = D.getMaxSlot();
		nbClasses = D.getClasses().size();
		courses = new Course[nbCourses];
		HashMap hmap = new HashMap();
		for(int i = 0; i < nbCourses; i++){
			courses[i] = D.getCourses().elementAt(i);
			hmap.put(courses[i],new Integer(i));
		}
		System.out.println("BackTrackSearch, nbCourses = " + nbCourses);
		forbiden = new int[nbCourses][maxDay+1][maxSlot+1];
		for(int i = 0; i < nbCourses; i++)
			for(int j = minDay; j <= maxDay; j++)
				for(int k = minSlot; k <= maxSlot; k++)
					forbiden[i][j][k] = 0;
		
		for(int i = 0; i < nbCourses; i++){
			Instructor I = courses[i].getInstructor();
			Vector<DaySlot> dayslots = I.getBusy();
			for(int j = 0; j < dayslots.size(); j++){
				DaySlot ds = dayslots.elementAt(j);
				int bsli = ds.getSlot();
				while(bsli >= minSlot && bsli > ds.getSlot()-courses[i].getNbrSlots()){
					forbiden[i][ds.getDay()][bsli]++;
					//if(i==0) System.out.println("forbiden " + bsli + " bsl = " + bsl + " minSlot = " + minSlot + " nbSlots = " + courses[i].getNbrSlots());
					bsli--;
				}
				
				//forbiden[i][ds.getDay()][bsli]++;
			}
			int nbSlots = courses[i].getNbrSlots();
			for(int d = minDay; d <= maxDay; d++){
				for(int sl = minSlot; sl <= maxSlot; sl++){
					if(sl + nbSlots == maxSlot)
						forbiden[i][d][sl]++;
				}
				forbiden[i][d][2]++;
			}
		}
		
		conflict = new boolean[nbCourses][nbCourses];
		for(int i = 0; i < nbCourses; i++){
			for(int j = 0; j < nbCourses; j++)
				conflict[i][j] = D.conflict(courses[i], courses[j]);
		}
		
		//nbCourses = 20;
		
		
		for(int i = 0; i < nbCourses-1;i++)
			for(int j = i+1; j < nbCourses; j++)
				if(conflict[i][j]){
					System.out.println("Detect conflict between course " + courses[i].getID() + " and course " + courses[j].getID());
				}
		
		for(int i = 0; i < nbCourses; i++){
			for(int j = minDay; j <= maxDay; j++){
				for(int k = minSlot; k <= maxSlot; k++)
					if(forbiden[i][j][k] > 0)
						System.out.println("Forbiden[" + i + "," + j + "," + k + "]");
			}
		}
		
		for(int i = 0; i < nbCourses; i++)
			courses[i].print();
		
		
//		try{
//			log = new BufferedWriter(new FileWriter("log.txt"));
//		}catch(IOException e){
//			System.out.println("io exception, cannot open file log.txt");
//		}
		TRY(0);
		
		
		

//		try{
//			log.close();
//		}catch(IOException e){
//			System.out.println("Cannot close log file");
//		}
//		
//		//writeLog("Total nbSolutions = " + nbSolutions);
		
		
	}
	
	public int[] getSolutionSlots(){
		return sol_slots;
	}
	public int[] getSolutionDays(){
		return sol_days;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}